#include <vector>
#include <stdexcept>
#include <iostream>
#include <fstream>
#include <string>

#define UDEBUG

// C(n, m)
auto C(std::size_t n, std::size_t m) -> std::vector<std::vector<std::size_t>> 
{
    if (n < m) throw std::logic_error{"In C(n, m), n < m!"};   
    std::vector<std::vector<std::size_t>> res {};

    if (m == 0)
    {
        res.emplace_back(std::vector<std::size_t>{});
    }
    else if (m == 1)
    {
        for (std::size_t i = 0; i < n; ++i)
            res.emplace_back(std::vector<std::size_t>{i});
    }
    else if (m == n)
    {
        res.emplace_back(std::vector<std::size_t>{});
        for (std::size_t i = 0; i < n; ++i)
            res.front().emplace_back(i);
    }
    else
    {
        auto subres1 {C(n - 1, m - 1)};
        for (std::vector<std::size_t>& v: subres1)
                v.emplace_back(n - 1);
        auto subres2 {C(n - 1, m)};
        
        for (std::vector<std::size_t>& v: subres1)
            res.emplace_back(std::move(v));
        for (std::vector<std::size_t>& v: subres2)
            res.emplace_back(std::move(v));
    }
    return res;
}

struct Data
{
    Data(std::string r, std::vector<std::size_t> t, std::vector<std::size_t> u):
        record{std::move(r)}, target{std::move(t)}, unknowns{std::move(u)} {}
    Data(Data&& data) noexcept:
        record{std::move(data.record)},
        target{std::move(data.target)},
        unknowns{std::move(data.unknowns)} {}

    std::string record{};
    std::vector<std::size_t> target{};
    std::vector<std::size_t> unknowns{};
};

std::ostream& operator << (std::ostream& os, const Data& data)
{
    os << "record:\n";
    os << data.record << '\n';
    
    os << "target:\n";
    for (const std::size_t c : data.target)
        os << c << ", ";
    os << '\n';

    os << "unknowns:\n";
    for (const std::size_t c : data.unknowns)
        os << c << ", ";

    os << std::ends; 
    return os;
}

std::vector<std::size_t> getNumbers(const std::string& content)
{
    std::size_t index {0};
    std::vector<std::size_t> numbers {};
    while (index < content.size())
    {
        if (content[index] == ',')
        {
            index += 1;
            continue;
        }
        // Find next ',' or end
        std::size_t pos {index + 1};
        while (true)
        {
            if (pos >= content.size() || content[pos] == ',')
                break;
            pos += 1;
        }
        numbers.emplace_back(std::stoull(&(content[index])));
        index = pos + 1;
    }
    return numbers;
}

Data getData(const std::string& line)
{
    // Get record
    std::size_t pos {line.find(' ')};
    std::string record {line.substr(0, pos)};

    // Find unknowns
    std::vector<std::size_t> unknowns{};
    for (std::size_t i = 0; i < record.size(); ++i)
    {
        if (record[i] == '?')
            unknowns.emplace_back(i);
    }

    // Get target
    std::vector<std::size_t> target {getNumbers(line.substr(pos + 1, line.size() - pos - 1))};

    return Data {std::move(record), std::move(target), std::move(unknowns)};
}

std::vector<std::size_t> getDamageds(const std::string& record)
{
    std::size_t begin {0};
    std::size_t end {0};
    std::vector<std::size_t> damageds {};
    std::size_t count {0};

    while (begin < record.size())
    {
        if (record[begin] != '#')
        {
            count = 0;
            begin += 1;
            continue;
        }
        // Find next not '#'
        end = begin + 1;
        while (true)
        {
            if (end >= record.size() || record[end] != '#')
                break;
            end += 1;
        }
        // [begin, end)
        damageds.emplace_back(end - begin);
        begin = end + 1;
    }

    return damageds;
}

bool isMeetCondition(const Data& data)
{
    std::vector<std::size_t> damageds {getDamageds(data.record)};
    
    // Compare
    if (damageds.size() != data.target.size())
        return false;
    for (std::size_t i = 0; i < damageds.size(); ++i)
        if (damageds[i] != data.target[i])
            return false;
    return true;
}

std::size_t getArrangementsCount(Data& data)
{
#ifndef UDEBUG
    std::cout << "=============================================" << std::endl;
#endif

    // Get choises
    std::size_t targetDamagedSize {0};
    for (std::size_t t : data.target)
        targetDamagedSize += t;
    
    std::size_t exitDamagedSize {0};
    for (const char ch : data.record)
        if (ch == '#') exitDamagedSize += 1;

#ifndef UDEBUG
    std::cout << "This data has " << exitDamagedSize << " '#', but it needs " << targetDamagedSize << std::endl;
#endif
    
    if (exitDamagedSize > targetDamagedSize) return 0;
    std::size_t needDamagedSize {targetDamagedSize - exitDamagedSize};
    
    auto choises {C(data.unknowns.size(), needDamagedSize)};

#ifndef UDEBUG
    std::cout << "Need to test " << choises.size() << " choises" << std::endl;
#endif
    std::size_t count {0};

    for (const std::vector<std::size_t>& choise : choises)
    {
        for (std::size_t i : choise)
            data.record[data.unknowns[i]] = '#';       

        if (isMeetCondition(data)) count += 1;

        for (std::size_t i : choise)
            data.record[data.unknowns[i]] = '.';
    }

#ifndef UDEBUG
    std::cout << "This data get " << count << " arrangements" << std::endl;
#endif

#ifndef UDEBUG
    std::cout << "=============================================" << std::endl;
#endif

    return count;
}

int main()
{
    std::ifstream infile {"./src/day12/input.txt"};
    std::string line {};
    std::vector<Data> datas {};

    while (std::getline(infile, line))
    {
        datas.emplace_back(getData(line));
        // std::cout << datas.back() << std::endl;
    }

    std::size_t sum {0};
    for (Data& data : datas)
        sum += getArrangementsCount(data);
    std::cout << sum << std::endl;

    return 0;
}